//每次找到离源点最近的一个本层顶点，然后以该顶点的出边进行松弛，反复迭代，最终得到源点到其余所有点的最短路径。


#define MAXVEX	9
#define	INFINITY	65535

typedef	int	Patharc[MAXVEX];			// 用于存储最短路径下标的数组
typedef int	ShortPathTable[MAXVEX];		// 用于存储到各点到源点v0的最短路径的权值和

void ShortestPath_Dijkstar(MGraph G, int V0, Patharc *P, ShortPathTable *D)	//v0为源点
{
	int v, w, k, min;
	int final[MAXVEX];		// final[w] = 1 表示已经求得顶点V0到Vw的最短路径，final数组的元素为标志位
	
	// 初始化数据
	for( v=0; v < G.numVertexes; v++ )
	{
		final[v] = 0;				// 全部顶点初始化为未找到最短路径
		(*D)[V] = G.arc[V0][v];		// 将与V0点有连线的顶点加上权值，(*D)用来缓存最短路径，若标志位final[k] = 1则可信
		(*P)[V] = 0;				// 初始化路径数组P为0
	}
	(*D)[V0] = 0;		// 源点V0至V0的路径为0
	final[V0] = 1;		// 源点V0至V0不需要求路径
	
	// 开始主循环，每次求得V0到某个V顶点的最短路径
	for( v=1; v < G.numVertexes; v++ )
	{
		min = INFINITY;							//无穷
		for( w=0; w < G.numVertexes; w++ )		//外循环，寻找到本层到源点最近的结点
		{
			if( !final[w] && (*D)[w]<min )		//标志位为0，且d[w]的值小于最短路径，重新赋值
			{
				k = w;							//当前结点的下标为k
				min = (*D)[w];
			}
		}
		final[k] = 1;	// 将目前找到的最近的顶点置1
		
		// 修正当前最短路径及距离
		for( w=0; w < G.numVextexes; w++ )		//内循环，k为最短路径结点的下标，w为k的下一个结点
		{
			if( !final[w] && (min+G.arc[k][w] < (*D)[w]) )		//如过final[w]=1，则不会进入；如果经由k结点到w的距离比缓存中的举例短，则更新缓存D[W]的值
			{
				(*D)[w] = min + G.arc[k][w];	// 修改当前路径长度
				(*p)[w] = k;					// 存放前驱顶点，k结点为w结点的前驱
			}
		}
	}
}